import datastructurelike.ListNode;
import datastructurelike.TreeNode;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Like
 * Date: 2021-04-14
 * Time: 9:35
 */

class Solution {
    public int fib(int n) {
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
            dp[i] %= 1000000007;
        }
        return dp[n];
    }
    //剑指 Offer 10- II. 青蛙跳台阶问题
    public int numWays(int n) {
        int a=1000000007;
        int[] dp = new int[n + 1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<n+1;i++){
            dp[i]=(dp[i-1]+dp[i-2])%a;
        }
        return dp[n];

    }


    int res,k;
    public int kthLargest(TreeNode root, int k) {
        int res=0;
        this.k=k;
        dfs(root);
        return res;


    }
    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.right);
        if(--k==0){
            res=root.val;
            return;
        }
        dfs(root.left);
    }
    public int maxDepth(TreeNode root) {
        if(root==null){return 0;}
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    //基于队列实现
    public int maxDepth2(TreeNode root) {
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        int depth=0;
        while (!deque.isEmpty()){
            int size=deque.size();
            while (size-->0){
                TreeNode cur=deque.pop();
                if(cur.left!=null){
                deque.push(cur.left);}
                if(cur.right!=null){
                deque.addLast(cur.right);}

            }
            depth++;
        }
        return depth;
    }
    public int[] singleNumbers(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<nums.length;i++){
            if (map.containsKey(nums[i])){
                map.remove(nums[i]);
            }else {
                map.put(nums[i],1);
            }

        }
        ArrayList<Integer> a = new ArrayList<>(map.keySet());
        int[] b=new int[a.size()];
        int j=0;
        Iterator<Integer> iterator=a.iterator();
        while(iterator.hasNext()){
            b[j]=iterator.next();
            j++;
        }
        return b;
    }
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ')
                i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ')
                i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }


    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        // 未形成窗口
        for(int i = 0; i < k; i++) {
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        // 形成窗口后
        for(int i = k; i < nums.length; i++) {
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }

    /*
     * 使用队列来是实现层序遍历
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(list);
        }
        return result;
    }

    //重建二叉树
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }

    public TreeNode reConstructBinaryTree2(int [] pre,int [] in){
        if(pre.length==0 || in.length==0)return null;
        TreeNode node = new TreeNode(pre[0]);
        for(int i=0;i<in.length;i++){
            if(pre[0]==in[i]){
                node.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i+1));
                node.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                break;
            }
        }
        return node;
    }

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            if(pHead1 == null || pHead2 == null)return null;
            ListNode p1 = pHead1;
            ListNode p2 = pHead2;
            while(p1!=p2){
                p1 = p1.next;
                p2 = p2.next;
                if(p1 != p2){
                    if(p1 == null) {
                        p1 = pHead2;
                    }
                    if(p2 == null) {
                        p2 = pHead1;
                    }
                }
            }
            return p1;

        }

    public void merge(int A[], int m, int B[], int n) {
        if(m==0 || n==0) {
            return;
        }


    }
    public boolean hasCycle(ListNode head) {
        ListNode slow = new ListNode(1);
        ListNode fast = new ListNode(1);
        while (slow!=null ){
            if(slow==fast) {
                return true;
            }
            slow=slow.next;
            fast=fast.next.next;

        }
        return false;
    }
    //最小的k个数

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        int length = input.length;
        if(k > length || k == 0){
            return result;
        }
        //降序排列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, (o1, o2) -> o2.compareTo(o1));
        for (int value : input) {
            if (maxHeap.size() != k) {
                maxHeap.offer(value);
            } else if (maxHeap.peek() > value) {
                maxHeap.poll();
                maxHeap.offer(value);
            }
        }
        result.addAll(maxHeap);
        return result;
    }
    
    //O(n)复杂度，遍历一遍，找到解就返回，没找到就放入map，key是值，value是下标加1；
    public static int[] twoSum(int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target - numbers[i]))
                return new int[]{map.get(target - numbers[i]), i+1};
            map.put(numbers[i], i+1);
        }
        return null;
    }
    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='[') {
                stack.push(']');
            } else if(c=='{') {
                stack.push('}');
            } else if(stack.empty() || stack.pop()!=c) {
                return false;
            }
        }
        return stack.empty();
    }

    public int Fibonacci(int n) {
        if(n==1) {
            return 1;
        }
        if(n==0) {
            return 0;
        }
        int sum=0;
        int two=0;
        int one=1;

        for(int i=2;i<=n;i++){
            sum=two+one;
            two=one;
            one=sum;
        }
        return sum;

    }

    //最大的k个数

    public static int findKth(int[] a, int n, int K) {
            dfs(a,0,n-1,K);
            return a[K - 1];
        }

    public static void dfs(int[] a, int left, int right,int k)
    {
        int temp = a[left];
        int ll = left;
        int rr = right;
        if(left == right) {
            return;
        }
        while(true)
        {
            while(a[right] < temp && left <right)
            {
                right--;
            }
            if(left == right){
                a[left] = temp;
                break;
            }
            a[left] = a[right];
            left++;
            //if(left == right)break;
            while(a[left] > temp && left < right)
            {
                left++;
            }
            if(left == right){
                a[left] = temp;
                break;
            }
            a[right] = a[left];
            right--;

        }
        if(right > k-1) {
            dfs(a,ll,right - 1,k);
        }
        if(right < k-1)dfs(a,right + 1,rr,k);
        if(right == k-1)return;
    }
    //子数组最大累加和
    public int maxsumofSubarray (int[] arr) {
        // write code here
        if(arr == null || arr.length == 0){
            return 0;
        }
        //dp[i] = dp[i-1] + arr[i]
        int sum = arr[0];
        int max = sum;

        for(int i = 1; i < arr.length; i ++){
            sum = sum > 0 ? sum + arr[i] : arr[i];
            max = Math.max(sum, max);
        }
        return max;
    }

    //列表环入口
    public ListNode EntryNodeOfLoop(ListNode pHead) {

            if(pHead == null){
                return null;
            }
            // 1.判断链表中有环,汇合点并不是环的入口节点
            ListNode l=pHead,r=pHead;
            boolean flag = false;
            while(r != null && r.next!=null){
                l=l.next;
                r=r.next.next;
                if(l==r){
                    flag=true;
                    break;
                }
            }
            if(!flag){
                return null;
            }else{
                // 2.得到环中节点的数目
                int n=1;
                r=r.next;
                while(l!=r){
                    r=r.next;
                    n++;
                }
                // 3.找到环中的入口节点，先让r走n步，即环中节点的数目，
                // 这里和倒数第k个节点一样，先让快指针走n步
                l=r=pHead;
                for(int i=0;i<n;i++){
                    r=r.next;
                }
                while(l!=r){
                    l=l.next;
                    r=r.next;
                }

                return l;
            }

    }




    public ListNode EntryNodeOfLoop2(ListNode pHead) {
        if (pHead==null || pHead.next == null) {
            return null;
        }
        HashMap<ListNode, Integer> map = new HashMap<>();
        ListNode node = pHead;
        while (node!=null){
            map.put(node, map.getOrDefault(node,0)+1);
            if(map.get(node)==2) {
                return node;
            }
            node = node.next;

        }
        return null;


    }

    //二叉树的层序遍历
    public ArrayList<Integer> layertraverset(TreeNode node){
        if(node == null ) {return null;}
        ArrayList<Integer> result = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode pop = queue.pop();
            result.add(pop.getVal());

            if(pop.getLeft()!=null){
                queue.add(pop.getLeft());
            }
            if(pop.getRight()!=null){
                queue.add(pop.getRight());
            }

        }
        return result;
    }

    //合并有序链表
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode prev = new ListNode();
        ListNode ans = prev;
        while(l1 != null && l2 != null){
            // prev指向较小的元素  ，然后再移动prev
            if(l1.val > l2.val){
                prev.next = l2;
                l2 = l2.next;
            }else{
                prev.next = l1;
                l1 = l1.next;
            }
            prev = prev.next;
        }
        //单一个链表为空时，将另一个直接补到最后
        if(l1 != null) {
            prev.next = l1;
        }
        else {
            prev.next = l2;
        }
        return ans.next;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int ans=solution.numWays(10);

        System.out.println(ans);
//        String s="012345";
//        System.out.println(s.substring(0,2));
            Integer o2=1;
            Integer o1=2;
            int ans2= o2.compareTo(o1);
        System.out.println(ans2);
    }




}